package br.com.rookgraph.branchreduce;

import br.com.rookgraph.Edge;
import br.com.rookgraph.Graph;
import br.com.rookgraph.Swap;
import br.com.rookgraph.articulacoes.ProcessadorArticulacoes;
import br.com.rookgraph.heuristica.Algoritm;
import br.com.rookgraph.heuristica.Plus2;
import br.com.rookgraph.utils.ArrayUtils;

public class BranchReducePlus implements Algoritm{

	/**
	 * @param args
	 */
	private Graph original;
	private Graph tree;
	private Plus2 heuristica;

	public BranchReducePlus(Graph original, Graph tree, Plus2 heuristica) {
		super();
		this.original = original;
		this.tree = tree;
		this.heuristica = heuristica;
	}

	@Override
	public Graph execute() {
		Graph graphBest = this.tree;
		Swap bestSwap = null;
		boolean replaceEdge;
		
		// temporariamente sem calculcar pois já estou fazendo para todos em ArenaAlgoritmo
		if (this.heuristica.consideraArticulacoes) {
			this.original.articulacoes = ProcessadorArticulacoes.identificarArticulacoes(original, 1);
		}
		
		do {
			bestSwap = null;
			replaceEdge = false;
			
			Edge[] cuttingList = createCuttingList();
			
			for (Edge edgeCut : cuttingList) {
				this.tree.removeEdge(edgeCut);
				
				Edge[] listRep = createReplacementListToCuttingEdge(edgeCut);
				
				this.tree.addEdge(edgeCut);
				
				for (Edge edgeRep : listRep) {
					Swap candidate = new Swap(edgeCut, edgeRep);
					candidate.setTree(graphBest);
					candidate.setOrignalGraph(original);
					candidate.consideraArticulacoes = this.heuristica.consideraArticulacoes;
					
					if (this.heuristica.considerarArticulacoes() )
						bestSwap = this.heuristica.getMelhorTroca2(bestSwap, candidate);
					else {
						bestSwap = this.heuristica.getMelhorTroca(bestSwap, candidate);
					}	
				}
			}
			
			if (bestSwap != null && isTrocaVantajosa(bestSwap)) {
				this.tree.swapEdge(bestSwap);
			//	System.out.println(bestSwap.getCut().origin+"<---->"+bestSwap.getCut().target+" -----> "+bestSwap.getReplace().origin+"<----->"+bestSwap.getReplace().target);
			    replaceEdge = true;
			   			    
			}
			
			if (isTreeBest(graphBest)) {
				try {
					graphBest = (Graph) this.tree.clone();
				} catch (CloneNotSupportedException e) {
					e.printStackTrace();
				}
			}
			
		} while (replaceEdge);
		
		
		return graphBest;
	}
	
	
	private boolean isTrocaVantajosa(Swap bestSwap) {
		boolean trocaVantajosa = false;
		int swapBeta = bestSwap.swapBeta();
		
		if (swapBeta < 0) {
			trocaVantajosa = true;
		} else if (swapBeta == 0) {
			int swapGama = bestSwap.swapGama();
			
			if (swapGama < 0) {
				trocaVantajosa = true;
			}
			else if (swapGama == 0) {
				int swapSigma = bestSwap.swapSigma();
				
				if (swapSigma > 0) {
					trocaVantajosa = true;
				} else if (swapSigma == 0) {
					int swapSigmaLinha = bestSwap.swapSigmaLinha();
					
					if (swapSigmaLinha < 0) {
						trocaVantajosa = true;
					}
				}
			}
		}
		
		return trocaVantajosa;
	}
	

	public boolean isTreeBest(Graph graphBest) {
		return this.tree.getBranchs().length < graphBest.getBranchs().length;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para corte com base na heuristica usada.
	 *
	 * @param listRep
	 * @return null se {@code listCut} estiver vazia ou a melhor aresta na lista. 
	 */
	protected Edge selectCutEdge(final Edge[] listCut) {
		Edge edgeCut = null;
		
		for (Edge candidate : listCut) {
			edgeCut = this.heuristica.selectForCut(candidate, edgeCut);
		}
		
		return edgeCut;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para Substituição,.
	 * Com base na heuristica usada.
	 * Retorn null se a lista vinher vazia, ou a aresta selecionada não for
	 * vantajosa sobre a aresta de cut.
	 *
	 * @param listRep
	 * @param edgeCut
	 * @return
	 */
	protected Edge selectEdgeFromReplamentList(final Edge[] listRep, Edge edgeCut) {
		Edge edgeRep = null;
		
		for (Edge candidate : listRep) {	
			edgeRep = this.heuristica.selectForRep(candidate, edgeRep);
		}
		
		return (edgeRep != null && this.heuristica.isVantajoso(edgeRep, edgeCut))? edgeRep : null;
	}

	public void calcParameters(Edge edge, boolean insert) {
		if (edge != null) {
			edge.sigma = this.tree.sigma(edge);

			edge.alfa = this.tree.alfa(edge);
			/* Só pra ganhar um pouco de desempenho  =) */
//			if(this.heuristica instanceof Plus){
				edge.beta = this.tree.beta(edge, insert);
				edge.gama = this.tree.gama(edge, insert);
				edge.sigmaLine = this.original.sigma(edge);
//			}
		}
	}

	protected Edge[] createReplacementListToCuttingEdge(final Edge arestaCut) {

		int[] seg1 = this.tree.reached(arestaCut.origin, new int[this.tree.getOrder()]);
		int[] seg2 = this.tree.reached(arestaCut.target, new int[this.tree.getOrder()]);

		// TODO verificar tamanho dessa lista por um teorema.
		Edge[] arestasRep = new Edge[seg1.length * seg2.length];

		int count = 0;

		/* Comparar arestas dos segmentos com as do grafo original */
		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {

				final Edge currentArest = new Edge(vSeg1, vSeg2);

				// if (!currentArest.equals(arestaCut) {  na heuritisca original a linha é essa
				if (!currentArest.equals(arestaCut) && (this.original.grau(vSeg1) > 1 && this.original.grau(vSeg2) > 1)) {

					if (!this.tree.hasEdge(vSeg1, vSeg2) && this.original.hasEdge(vSeg1, vSeg2)) {
                        
						//  veio para cá
						
					    this.tree.addEdge(currentArest);

						calcParameters(currentArest, true);

						this.tree.removeEdge(currentArest);

						if (!ArrayUtils.contains(currentArest, arestasRep)){
							arestasRep[count++] = currentArest;
						}
					}
				}
			}
		}

		Edge[] listRep = new Edge[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}

	/**
	 * Cria a lista de arestas candidatas a corte.
	 *
	 * @return
	 */
	protected Edge[] createCuttingList() {
		int order = tree.getOrder();
		int count = 0;
		Edge[] edgesCut = new Edge[order * order];

		for (int branch : this.tree.getBranchs()) {
			for (int adjacente : this.tree.getAdjacentes(branch)) { 
				   Edge candidata = new Edge(branch, adjacente);
				
				// if (!conteins(candidata, edgesCut)) { na algoritimo original a linha é essa
				if (!ArrayUtils.contains(candidata, edgesCut)  && (this.original.grau(adjacente) > 1)){
					calcParameters(candidata, false);
					edgesCut[count++] = candidata;
				}
			} 
		}

		Edge[] listCut = new Edge[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		return listCut;
	}


	public Graph getOriginal() {
		return original;
	}

	public void setOriginal(Graph original) {
		this.original = original;
	}

	public Graph getTree() {
		return tree;
	}

	public void setTree(Graph tree) {
		this.tree = tree;
	}


}
